{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Level Order Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: levelOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的层序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> ，返回其节点值的 <strong>层序遍历</strong> 。 （即逐层地，从左到右访问所有节点）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg\" style=\"width: 277px; height: 302px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,9,20,null,null,15,7]\n",
    "<strong>输出：</strong>[[3],[9,20],[15,7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[0, 2000]</code> 内</li>\n",
    "\t<li><code>-1000 &lt;= Node.val &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-level-order-traversal](https://leetcode.cn/problems/binary-tree-level-order-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-level-order-traversal](https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        processing_lst = [root]\n",
    "        curr_processing = []\n",
    "        ret = [[root.val]]\n",
    "        i = 0\n",
    "        while i<=len(processing_lst):\n",
    "            if i == len(processing_lst):\n",
    "                if len(curr_processing) > 0:\n",
    "                    ret.append([x.val for x in curr_processing])\n",
    "                    processing_lst.extend(curr_processing)\n",
    "                    curr_processing = []\n",
    "                else: \n",
    "                    break\n",
    "            else:\n",
    "                curr_node = processing_lst[i]\n",
    "                if curr_node.left is not None:\n",
    "                    curr_processing.append(curr_node.left)\n",
    "                if curr_node.right is not None:\n",
    "                    curr_processing.append(curr_node.right)\n",
    "                i+= 1\n",
    "                \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        ret, ret_level, queue = [], [], []\n",
    "        level_last = -1\n",
    "        if root:\n",
    "            queue.append((root, 0))\n",
    "        while queue:\n",
    "            node, level = queue.pop(0)\n",
    "            if level != level_last:\n",
    "                if ret_level:\n",
    "                    ret.append(ret_level)\n",
    "                ret_level = []\n",
    "                level_last = level\n",
    "            ret_level.append(node.val)\n",
    "            if node.left:\n",
    "                queue.append((node.left, level + 1))\n",
    "            if node.right:\n",
    "                queue.append((node.right, level + 1))\n",
    "        if ret_level:\n",
    "            ret.append(ret_level)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if root == None:\n",
    "            return result\n",
    "        up_layer = [root]\n",
    "        layer_vals = [root.val]\n",
    "        result.append(layer_vals)\n",
    "        while len(up_layer)>0:\n",
    "            layer_values = []\n",
    "            next_layer = []\n",
    "            for node in up_layer:\n",
    "                if (node.left != None):\n",
    "                    next_layer.append(node.left)\n",
    "                    layer_values.append(node.left.val)\n",
    "                if (node.right != None):\n",
    "                    next_layer.append(node.right)\n",
    "                    layer_values.append(node.right.val)\n",
    "            if (len(layer_values)>0):\n",
    "                result.append(layer_values)\n",
    "            up_layer = next_layer\n",
    "        return result\n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        if root is None:\n",
    "            return result\n",
    "\n",
    "        stack = [root, None]\n",
    "        work = []\n",
    "        while stack:\n",
    "            now = stack.pop(0)\n",
    "            if now is None:\n",
    "                result.append(work)\n",
    "                work = []\n",
    "                if stack:\n",
    "                    stack.append(None)\n",
    "            else:\n",
    "                work.append(now.val)\n",
    "                if now.left:\n",
    "                    stack.append(now.left)\n",
    "                if now.right:\n",
    "                    stack.append(now.right)\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        self.traversal(root,0,res)\n",
    "        return res\n",
    "    def traversal(self,root,depth,res):\n",
    "        if root:\n",
    "            if depth>=len(res):\n",
    "                res+=[[]]\n",
    "            res[depth] +=[root.val]\n",
    "            self.traversal(root.left,depth+1,res)\n",
    "            self.traversal(root.right,depth+1,res)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result=[]\n",
    "\n",
    "\n",
    "    def levelOrder(self, root):\n",
    "            \"\"\"\n",
    "            :type root: TreeNode\n",
    "            :rtype: List[List[int]]\n",
    "            \"\"\"\n",
    "            if root == None:\n",
    "                return []\n",
    "            if root.left == None and root.right == None:\n",
    "                return [[root.val]]\n",
    "            lst = [[root.val]]\n",
    "            lft = self.levelOrder(root.left)\n",
    "            rgt = self.levelOrder(root.right)\n",
    "            while lft and rgt:\n",
    "                lst.append(lft.pop(0) + rgt.pop(0))\n",
    "            if lft:\n",
    "                lst.extend(lft)\n",
    "            if rgt:\n",
    "                lst.extend(rgt)\n",
    "            return lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def levelOrder(self, root: 'TreeNode') -> 'List[List[int]]':\n",
    "        if root is None: return []\n",
    "        ls = []\n",
    "        q = Queue()\n",
    "        q.put((root, 0))\n",
    "        level = []\n",
    "        cur_depth = 0\n",
    "        # cnt: 访问了队列中的多少个数\n",
    "        while not q.empty():\n",
    "            tp = q.get()\n",
    "            cur = tp[0]\n",
    "            new_depth = tp[1]\n",
    "            if new_depth > cur_depth:\n",
    "                cur_depth = new_depth\n",
    "                ls.append(level)\n",
    "                level = []\n",
    "            if cur is None: continue\n",
    "            level.append(cur.val)\n",
    "            l, r = cur.left, cur.right\n",
    "            q.put((cur.left, cur_depth+1))\n",
    "            q.put((cur.right, cur_depth+1))\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        self.result = []\n",
    "        self._dfs(root, 0)\n",
    "        return self.result\n",
    "    \n",
    "    def _dfs(self, node, level):\n",
    "        if not node: return # 递归结束条件\n",
    "\n",
    "        if len(self.result) < level + 1:\n",
    "            self.result.append([])\n",
    "\n",
    "        self.result[level].append(node.val)\n",
    "\n",
    "        self._dfs(node.left, level + 1)\n",
    "        self._dfs(node.right, level + 1)\n",
    "            \n",
    "\n",
    "#         if not root: return []\n",
    "        \n",
    "#         q = [root]\n",
    "#         res = []\n",
    "        \n",
    "#         while q:\n",
    "#             len_q = len(q)\n",
    "#             cur = []\n",
    "#             for _ in range(len_q):\n",
    "#                 node = q.pop(0)\n",
    "#                 cur.append(node.val)\n",
    "#                 if node.left: q.append(node.left)\n",
    "#                 if node.right: q.append(node.right)   \n",
    "#             res.append(cur)\n",
    "#         return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        nodes = [root]\n",
    "        index = 1\n",
    "        while(nodes):\n",
    "            cache = []\n",
    "            length = 0\n",
    "            while(index):\n",
    "                node = nodes.pop(0)\n",
    "                cache.append(node.val)\n",
    "                if(node.left):\n",
    "                    nodes.append(node.left)\n",
    "                    length += 1\n",
    "                if(node.right):\n",
    "                    nodes.append(node.right)\n",
    "                    length += 1\n",
    "                index -= 1\n",
    "            index += length\n",
    "            res.append(cache)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        ans = list()\n",
    "        if not root:\n",
    "            return ans\n",
    "        current_node = [root]\n",
    "        while current_node:\n",
    "            current_ans = []\n",
    "            next_level = []\n",
    "            for i in current_node:\n",
    "                current_ans.append(i.val)\n",
    "                if i.left:\n",
    "                    next_level.append(i.left)\n",
    "                if i.right:\n",
    "                    next_level.append(i.right)\n",
    "            ans.append(current_ans)\n",
    "            current_node = next_level\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode):\n",
    "        queue = Queue()\n",
    "        queue.put_nowait(root)\n",
    "        orders = list()\n",
    "        if root is None:\n",
    "            return orders\n",
    "        while queue.empty() is False:\n",
    "            level_queue = Queue()\n",
    "            level = list()\n",
    "            while queue.empty() is False:\n",
    "                cursor = queue.get_nowait()\n",
    "                if cursor is None:\n",
    "                    continue\n",
    "                level.append(cursor.val)\n",
    "                level_queue.put_nowait(cursor.left)\n",
    "                level_queue.put_nowait(cursor.right)\n",
    "            if level:\n",
    "                orders.append(level)\n",
    "            queue = level_queue\n",
    "        return orders\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        res=[]\n",
    "        temp=[root]\n",
    "        te=[root]\n",
    "        if not root:\n",
    "            return []\n",
    "        res.append([root.val])\n",
    "        while te:\n",
    "            cur=te\n",
    "            te=[]\n",
    "            res_=[]\n",
    "            for c_tree in cur:\n",
    "                if c_tree.left:\n",
    "                    temp.append(c_tree.left)\n",
    "                    te.append(c_tree.left)\n",
    "                if c_tree.right:\n",
    "                    temp.append(c_tree.right)\n",
    "                    te.append(c_tree.right)\n",
    "            if te==[]:\n",
    "                break\n",
    "            else:\n",
    "                for i in te:\n",
    "                    res_.append(i.val)\n",
    "                res.append(res_)\n",
    "        \n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        tr=[root]#下一层首先为root\n",
    "        tv=[]\n",
    "        av=[]\n",
    "        while tr:#当没有下一层时，迭代结束\n",
    "            nr=[]#记录下一层的节点\n",
    "            for i in tr:#当前层的每一个节点，记录它的左右子树，即下一层\n",
    "                if i.left:#记录非空子树\n",
    "                    nr.append(i.left)\n",
    "                if i.right:\n",
    "                    nr.append(i.right)\n",
    "                tv.append(i.val)#记录当前节点值\n",
    "            tr=nr[:]#遍历完下一层节点，交给tr\n",
    "            av.append(tv)#保存当前层所有节点值\n",
    "            tv=[]#初始化值列表\n",
    "        return av\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        ans  = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        def bfs(node):\n",
    "            que = deque()\n",
    "            que.append(node)\n",
    "            while que:\n",
    "                l = len(que)\n",
    "                temp = []\n",
    "                for ii in range(l):\n",
    "                    cur  = que.popleft()\n",
    "                    temp.append(cur.val)\n",
    "                    if cur.left:\n",
    "                        que.append(cur.left)\n",
    "                    if cur.right:\n",
    "                        que.append(cur.right)\n",
    "                ans.append(temp)\n",
    "        bfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        return level_order(root)\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def level_order(root: TreeNode) -> List[List[int]]:\n",
    "    if not root:\n",
    "        return []\n",
    "    r, l = [], [root]\n",
    "    while l:\n",
    "        r.append([n.val for n in l])\n",
    "        nl = []\n",
    "        for n in l:\n",
    "            if n.left:\n",
    "                nl.append(n.left)\n",
    "            if n.right:\n",
    "                nl.append(n.right)\n",
    "        l = nl\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        res=list()\n",
    "        que=list()\n",
    "        if root is None:\n",
    "            return res\n",
    "        \n",
    "        que.append(root)\n",
    "        while que:\n",
    "            level=list()\n",
    "            n=len(que)\n",
    "            for _ in range(n):\n",
    "                node=que[0]\n",
    "                que=que[1:]\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    que.append(node.left)\n",
    "                if node.right: \n",
    "                    que.append(node.right)\n",
    "            res.append(level)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.results = []\n",
    "\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        self.helper(root, 0)\n",
    "        return self.results\n",
    "\n",
    "    def helper(self, node: TreeNode, level):\n",
    "        if len(self.results) == level:\n",
    "            self.results.append([])\n",
    "        \n",
    "        self.results[level].append(node.val)\n",
    "        \n",
    "        if node.left is not None:\n",
    "            self.helper(node.left, level + 1)\n",
    "        if node.right is not None:\n",
    "            self.helper(node.right, level + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        res = []\n",
    "        \n",
    "        def traverse(root, level):\n",
    "            if not root:\n",
    "                return\n",
    "            if level == len(res):\n",
    "                res.append([root.val])\n",
    "            else:\n",
    "                res[level].append(root.val)\n",
    "            traverse(root.left, level + 1)\n",
    "            traverse(root.right, level + 1)\n",
    "        \n",
    "        traverse(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        res = list()\n",
    "        node_list = [root]\n",
    "        while node_list:\n",
    "            layer = list()\n",
    "            num = len(node_list)\n",
    "            for _ in range(num):\n",
    "                node = node_list.pop(0)\n",
    "                layer.append(node.val)\n",
    "                if node.left:\n",
    "                    node_list.append(node.left)\n",
    "                if node.right:\n",
    "                    node_list.append(node.right)\n",
    "            res.append(layer)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "\tdef levelOrder(self, root):\n",
    "\t\tif root==None: # python和C++一样，都有not\n",
    "\t\t\treturn []\n",
    "\t\tres = []\n",
    "\t\tqueue = [root]\n",
    "\t\twhile queue:\n",
    "\t\t\t# 获取当前队列的长度，这个长度相当于 当前这一层的节点个数\n",
    "\t\t\tsize = len(queue)\n",
    "\t\t\tres.append([])\n",
    "\t\t\t# 将队列中的元素都拿出来(也就是获取这一层的节点)，放到临时list中\n",
    "\t\t\t# 如果节点的左/右子树不为空，也放入队列中\n",
    "\t\t\tfor _ in range(size):\n",
    "\t\t\t\tr = queue.pop(0)\n",
    "\t\t\t\tres[-1].append(r.val)\n",
    "\t\t\t\tif r.left:\n",
    "\t\t\t\t\tqueue.append(r.left)\n",
    "\t\t\t\tif r.right:\n",
    "\t\t\t\t\tqueue.append(r.right)\n",
    "\t\t\t# 将临时list加入最终返回结果中\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        q = collections.deque()\n",
    "        q.append(root)\n",
    "\n",
    "        while q:\n",
    "            qLen = len(q)\n",
    "            level = []\n",
    "            for i in range(qLen):\n",
    "                node = q.popleft()\n",
    "                if node:\n",
    "                    level.append(node.val)\n",
    "                    q.append(node.left)\n",
    "                    q.append(node.right)\n",
    "\n",
    "            if level:\n",
    "                res.append(level)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        results=[]\n",
    "        if not root:\n",
    "            return results\n",
    "        from collections import deque\n",
    "        que=deque([root])\n",
    "        while que:\n",
    "            result=[]\n",
    "            for _ in range(len(que)):\n",
    "                cur=que.popleft()\n",
    "                result.append(cur.val)\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "            results.append(result)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            t = []\n",
    "            for i in range(len(stack)):\n",
    "                node = stack.pop(0)\n",
    "                t.append(node.val)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            res.append(t)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        a = [root]\n",
    "        c,d = [], []\n",
    "        c.append(root.val)\n",
    "        d.append([root.val])\n",
    "        # print(d)\n",
    "        i, j, m, k = 0, 1, 0, 0\n",
    "        while a:\n",
    "            if a is None:\n",
    "                return []\n",
    "            b = a.pop(0)\n",
    "            k += 1\n",
    "            print(b.val)\n",
    "            if b.val not in d[m] or k == len(d[m]):\n",
    "                k = 0\n",
    "                d.append(c[j:i+1])\n",
    "                m += 1\n",
    "                j = i + 1\n",
    "                print(d)\n",
    "            if b.left is not None:\n",
    "                a.append(b.left)\n",
    "                c.append(b.left.val)\n",
    "                i += 1\n",
    "            if b.right is not None:\n",
    "                a.append(b.right)\n",
    "                c.append(b.right.val)\n",
    "                i += 1\n",
    "        while [] in d:\n",
    "            d.remove([])\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 递归法\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def eachlevel(root, depth):\n",
    "            if root == None:\n",
    "                return\n",
    "            if len(res)==depth:\n",
    "                res.append([])\n",
    "            res[depth].append(root.val)\n",
    "            if root.left:\n",
    "                eachlevel(root.left,depth+1)\n",
    "            if root.right:\n",
    "                eachlevel(root.right,depth+1)\n",
    "        eachlevel(root,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        cur, res = [root], []\n",
    "        while cur:\n",
    "            lay, layval = [], []\n",
    "            for node in cur:\n",
    "                layval.append(node.val)\n",
    "                if node.left: lay.append(node.left)\n",
    "                if node.right: lay.append(node.right)\n",
    "            cur = lay\n",
    "            res.append(layval)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        queue = [root]\n",
    "        res = []\n",
    "        while queue:\n",
    "            res.append([node.val for node in queue])\n",
    "            lr = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    lr.append(node.left)\n",
    "                if node.right:\n",
    "                    lr.append(node.right)\n",
    "            queue = lr\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        res, queue = [], []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop(0)\n",
    "                tmp.append(node.val)\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res.append(tmp)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        \n",
    "        while queue:\n",
    "            tmp = []\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                r = queue.pop(0)\n",
    "                tmp.append(r.val)\n",
    "                if r.left:\n",
    "                    queue.append(r.left)\n",
    "                if r.right:\n",
    "                    queue.append(r.right)\n",
    "            res.append(tmp)\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        path = []\n",
    "        queue = deque([(root, 1)])\n",
    "        while len(queue) > 0:\n",
    "            current_node, depth = queue.popleft()\n",
    "            path.append((current_node, depth))\n",
    "            if current_node:\n",
    "                if current_node.left:\n",
    "                    next_node = current_node.left\n",
    "                    queue.append((next_node, depth+1))\n",
    "                if current_node.right:\n",
    "                    next_node = current_node.right\n",
    "                    queue.append((next_node, depth+1))\n",
    "        max_depth = path[-1][1]\n",
    "        results = []\n",
    "        for i in range(max_depth):\n",
    "            temp_layer = []\n",
    "            for j in path:\n",
    "                if i+1 == j[1]:\n",
    "                    temp_layer.append(j[0].val)\n",
    "            results.append(temp_layer)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        res = []\n",
    "        while queue:\n",
    "            print(res)\n",
    "            level = []\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                level.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "            res.append(level)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root:\n",
    "            curr_node = [{0: root}]\n",
    "            result_node = [{0: root}]\n",
    "            while curr_node:\n",
    "                node = self.get_firstval_dict(curr_node.pop(0))\n",
    "                if node[1].left:\n",
    "                    curr_node.append({node[0] + 1: node[1].left})\n",
    "                    result_node.append({node[0] + 1: node[1].left})\n",
    "                if node[1].right:\n",
    "                    curr_node.append({node[0] + 1: node[1].right})\n",
    "                    result_node.append({node[0] + 1: node[1].right})\n",
    "            return self.get_item_com(result_node)\n",
    "\n",
    "        else:\n",
    "            return []\n",
    "\n",
    "    def get_firstval_dict(self, dict_arr):\n",
    "        for key, val in dict(dict_arr).items():\n",
    "            return [key, val]\n",
    "\n",
    "    def get_item_com(self, dict_list):\n",
    "        ret_val = {}\n",
    "        ret_list = []\n",
    "        temp = []\n",
    "        for a in dict_list:\n",
    "            for k, v in a.items():\n",
    "                ret_val[k] = list(ret_val.get(k, [])) + [v.val]\n",
    "\n",
    "        for key, v in ret_val.items():\n",
    "            ret_list.append(v)\n",
    "        return ret_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "class Solution:\n",
    "    def levelOrder(self, root: TreeNode) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def lo(root, level, result):\n",
    "            result = copy.copy(result)\n",
    "            if root:\n",
    "                try:\n",
    "                    result[level].append(root.val)\n",
    "                except:\n",
    "                    result.insert(level, [])\n",
    "                    result[level].append(root.val)\n",
    "                result = lo(root.left, level + 1, result)\n",
    "                result = lo(root.right, level + 1, result)\n",
    "            return result\n",
    "        return lo(root, 0, [])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if root==None:\n",
    "            return []\n",
    "        def digui(lis,head):\n",
    "            if lis==[]:\n",
    "                return head\n",
    "            liss=[];liss2=[]\n",
    "            for i in lis:\n",
    "                liss.append(i.val)\n",
    "                if i.left!=None:\n",
    "                    liss2.append(i.left)\n",
    "                if i.right!=None:\n",
    "                    liss2.append(i.right)\n",
    "            return digui(liss2,head+[liss])\n",
    "        return digui([root],[])        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        max_depth = self.rootDepth(root)\n",
    "        result = [[] for i in range(max_depth)]\n",
    "        result[0].append(root)\n",
    "        for i in range(len(result)):\n",
    "            for j in range(len(result[i])):\n",
    "                #print(type(j.left))\n",
    "                if result[i][j].left is not None:\n",
    "                    #print('left',j.left)\n",
    "                    result[i+1].append(result[i][j].left)\n",
    "                if result[i][j].right is not None:\n",
    "                    #print(j.right)\n",
    "                    result[i+1].append(result[i][j].right)\n",
    "                result[i][j] = result[i][j].val\n",
    "                #print('1',j,result[i])\n",
    "        #print(result)\n",
    "        return result\n",
    "\n",
    "    def rootDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        depth = 0\n",
    "        left_depth = 0\n",
    "        right_depth = 0\n",
    "        if root:\n",
    "            depth += 1\n",
    "            #print('root')\n",
    "        if root.left:\n",
    "            left_depth += self.rootDepth(root.left)\n",
    "        if root.right:\n",
    "            right_depth += self.rootDepth(root.right)\n",
    "        #print(depth,left_depth,right_depth)\n",
    "        return depth + max(left_depth,right_depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        queue = [root]\n",
    "        res = []\n",
    "        \n",
    "        def dfs(idx, r):\n",
    "            if len(res) - 1 < idx:\n",
    "                res.append([])\n",
    "            res[idx].append(r.val)\n",
    "            if r.left:\n",
    "                dfs(idx+1, r.left)\n",
    "            if r.right:\n",
    "                dfs(idx+1, r.right)\n",
    "        dfs(0, root)\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
